public class MonotoneIncreasingDigits0108_738 {

    //暴力 超时
//    public int monotoneIncreasingDigits(int n) {
//        if(n<10) return n;
//        for (int i = n; i > 10; i--) {
//            if(checkNum(i)) return i;
//        }
//        return 9;
//
//    }
//
//    private boolean checkNum(int i) {
//        String s = String.valueOf(i);
//        char[] chars = s.toCharArray();
//
//        for (int j = chars.length-2; j > 0; j--) {
//            if(chars[j] < chars[j-1]) return false;
//        }
//        return true;
//    }


    //贪心算法
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();


        for (int i = chars.length-1; i >0 ; i--) {
            if(chars[i] < chars[i-1]){
                chars[i-1] = (char) (chars[i-1] - 1);
                for (int j = i; j < chars.length; j++) {
                    chars[j] = '9';
                }
            }
        }



        return Integer.parseInt(String.valueOf(chars));

    }
}
